package tree;

/**
 * 线索化二叉树的操作
 * @Auther Jun jie Yi
 * @Date 10:09 2021/7/17
 */
public class ThreadBinaryTreeDemo {

    static HeroNode pre = null;//保存线索化二叉树的前驱结点

    public static void main(String[] args) {
        //构造一个结构
        HeroNode root = new ThreadBinaryTreeDemo().new HeroNode(1, "宋江");
        root.left = new ThreadBinaryTreeDemo().new HeroNode(2, "吴用");
        root.right = new ThreadBinaryTreeDemo().new HeroNode(3, "卢梭");
        root.right.right = new ThreadBinaryTreeDemo().new HeroNode(4, "林冲");

        threadPostHeroNode(root);

        //线索化二叉树之后需要用新的方式来遍历二叉树
        //threadedPreList(root);
    }

    //用前序遍历的方法进行线索化二叉树
    public static void threadPreHeroNode(HeroNode node) {
        //如果 node == null 不能线索化
        if(node == null) {
            return;
        }
        //-----------------------------------------------------
        //2.线索化当前结点
        //先处理当前结点的前驱结点
        if(node.left == null) {
            //让当前节点的左指针指向前驱结点
            node.left = pre;
            //修改当前结点的左指针类型
            node.leftType = 1;
        }
        //处理后继结点(这个是在下次处理)
        if(pre != null && pre.right == null) {
            //让前驱结点指向当前结点
            pre.right = node;
            //修改前驱结点的右指针类型
            pre.rightType = 1;
        }
        //每次处理一个结点之后存储当前结点作为下一个结点的前驱结点
        pre = node;
        //----------------------------------------------------
        //1.线索化左子树
        if(node.left != null) {
            threadInfixHeroNode(node.left);
        }
        //3.线索化右子树
        if(node.right != null) {
            threadInfixHeroNode(node.right);
        }
    }

    //用中序遍历的方法进行线索化二叉树
    public static void threadInfixHeroNode(HeroNode node) {
        //如果 node == null 不能线索化
        if(node == null) {
            return;
        }
        //1.线索化左子树
        if(node.left != null) {
            threadInfixHeroNode(node.left);
        }
        //-----------------------------------------------------
        //2.线索化当前结点
        //先处理当前结点的前驱结点
        if(node.left == null) {
            //让当前节点的左指针指向前驱结点
            node.left = pre;
            //修改当前结点的左指针类型
            node.leftType = 1;
        }
        //处理后继结点(这个是在下次处理)
        if(pre != null && pre.right == null) {
            //让前驱结点指向当前结点
            pre.right = node;
            //修改前驱结点的右指针类型
            pre.rightType = 1;
        }
        //每次处理一个结点之后存储当前结点作为下一个结点的前驱结点
        pre = node;
        //----------------------------------------------------
        //3.线索化右子树
        if(node.right != null) {
            threadInfixHeroNode(node.right);
        }
    }

    //用后序遍历的方法进行线索化二叉树
    public static void threadPostHeroNode(HeroNode node) {
        //如果 node == null 不能线索化
        if (node == null) {
            return;
        }
        //1.线索化左子树
        if (node.left != null) {
            threadInfixHeroNode(node.left);
        }
        //3.线索化右子树
        if (node.right != null) {
            threadInfixHeroNode(node.right);
        }
        //-----------------------------------------------------
        //2.线索化当前结点
        //先处理当前结点的前驱结点
        if (node.left == null) {
            //让当前节点的左指针指向前驱结点
            node.left = pre;
            //修改当前结点的左指针类型
            node.leftType = 1;
        }
        //处理后继结点(这个是在下次处理)
        if (pre != null && pre.right == null) {
            //让前驱结点指向当前结点
            pre.right = node;
            //修改前驱结点的右指针类型
            pre.rightType = 1;
        }
        //每次处理一个结点之后存储当前结点作为下一个结点的前驱结点
        pre = node;
        //-------------------------------------------------
    }

    //---------------------------------------------------------------------------------
    //遍历前序线索化的二叉树
    public static void threadedPreList(HeroNode root) {
        //定义一个变量，存储当前遍历的结点，从root开始
        HeroNode node = root;
        while (node != null){
            //循环的找到leftType == 1的结点
            //后面随着遍历而变化，因为leftType==1，说明该结点是按照线索化处理后的有效结点
            while (node.leftType == 0){
                //打印当前结点
                System.out.println(node.name);
                node = node.left;
            }
            //如果当前结点的右指针指向的是后继结点，就一直输出
            while (node.rightType == 1){
                //打印当前结点
                System.out.println(node.name);
                //获取到当前结点的后继结点
                node = node.right;
            }
            System.out.println(node.name);
            //替换这个遍历的结点
            node  = node.right;
        }
    }

    //遍历中序线索化的二叉树
    public static void threadedInfixList(HeroNode root) {
        //定义一个遍历，存储当前遍历的结点，从 root 开始
        HeroNode node = root;
        while(node != null) {
            //先找到最左边的结点
            while(node.leftType == 0) {
                node = node.left;
            }
            System.out.println(node.name);
            while(node.rightType == 1) {
                node = node.right;
                System.out.println(node.name);
            }
            node = node.right;
        }
    }

    //后续遍历线索二叉树，按照后继方式遍历（思路：后序遍历开始节点是最左节点）
    void postThreadList(HeroNode root) {
        //1、找后序遍历方式开始的节点
        HeroNode node = root;
        while(node != null && node.leftType == 0) {
            node = node.left;
        }

        HeroNode preNode = null;
        while(node != null) {
            //右节点是线索
            if(node.rightType == 1) {
                System.out.print(node.name);
                preNode = node;
                node = node.right;

            } else {
                //如果上个处理的节点是当前节点的右节点
                if(node.right == preNode) {
                    System.out.print(node.name);
                    if(node == root) {
                        return;
                    }

                    preNode = node;
                    node = node.father;

                } else {    //如果从左节点的进入则找到有子树的最左节点
                    node = node.right;
                    while(node != null && node.leftType == 0) {
                        node = node.left;
                    }
                }
            }
        }
    }

    //--------------------------------------------------------------------
    class HeroNode {
        int no;
        String name;
        HeroNode left;
        HeroNode right;
        HeroNode father; //父节点的指针（为了后序线索化使用：这里创建树的时候还必须将父节点存入）
        int leftType; //如果是 0 表示指向左子树，如果是 1 表示指向前驱结点
        int rightType; //如果是 0 表示指向右子树，如果是 1 表示指向后继结点
        public HeroNode(int no, String name) {
            this.no = no;
            this.name = name;
        }
    }
}
